package com.ztom.top100;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

/**
 * 课程表
 * <p>
 * https://leetcode-cn.com/problems/course-schedule/
 *
 * @author ZhangTao
 */
public class Code61CanFinish {

    /**
     * BFS
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        // 构建入度表
        int[] in = new int[numCourses];
        // 将节点挂起来
        Map<Integer, List<Integer>> nexts = new HashMap<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            nexts.put(i, new ArrayList<>());
        }
        // 0 位置依赖 1 位置, 0 位置入度+1, 0 挂在 1 下
        for (int[] p : prerequisites) {
            in[p[0]]++;
            nexts.get(p[1]).add(p[0]);
        }
        // 找到入度为 0 的顶点, 入队列
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            // 入度为 0 说明课程可以完成
            numCourses--;
            for (Integer c : nexts.get(course)) {
                if (--in[c] == 0) {
                    queue.add(c);
                }
            }
        }
        return numCourses == 0;
    }

    /**
     * DFS
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> nexts = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) {
            nexts.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            nexts.get(p[1]).add(p[0]);
        }
        int[] flags = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i, nexts, flags)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int i, List<List<Integer>> nexts, int[] flags) {
        if (flags[i] == 1) {
            // 正常完成的课程
            return true;
        }
        if (flags[i] == -1) {
            // 完不成的课程(有环)
            return false;
        }
        flags[i] = -1;
        for (Integer c : nexts.get(i)) {
            if (!dfs(c, nexts, flags)) {
                return false;
            }
        }
        flags[i] = 1;
        return true;
    }
}
